#pragma once

#include <assert.h>
#include <string>
#include <iostream>
#include <vector>
#include <stdexcept>

#include "Node.h"

class Tree
{
	int decisionLevels_;
	std::vector<TNode> nodes_;
	typedef std::vector<unsigned int>::size_type DataPointIndex;

public:
	Tree(int decisionLevels):decisionLevels_(decisionLevels)
	{
		if (decisionLevels<0)
			throw std::runtime_error("Tree can't have less than 0 decision level");

		if (decisionLevels>19)
			throw std::runtime_error("Tree can't have more than 19 decision level");

		nodes_.resize(1<<(decisionLevels+1)-1);
	}

	std::vector<TNode>& GetNodes(){return nodes_;}

	int NodeCount()const
	{
		return nodes_.size();
	}

	TNode& GetNode(int index)
	{
		return nodes_[index];
	}

	static DataPointIndex Partition(std::vector<float>&keys, std::vector<unsigned int>& values, DataPointIndex i0, DataPointIndex i1, float threshold)
	{
		assert(i1>i0);
		int i = (int)(i0);
		int j = int (i1-1);

		while (i!=j)
		{
			if (keys[i]>=threshold)
			{
				float key = keys[i];
				unsigned int value = values[i];

				keys[i] = keys[j];
				values[i] = values[j];

				keys[j] = key;
				values[j] = value;

				j--;
			}
			else
			{
				i++;
			}
		}

		return keys[i]>=threshold ? i:i+1;
	}


};
